class TreeNode {
    public value!: number;
    public left?: TreeNode;
    public right?: TreeNode;

    constructor(value: number) {
        this.value = value;
    }

    public add(newNode: TreeNode) {
        if (newNode.value < this.value) {
            if (this.left === undefined) {
                this.left = newNode;
            }
            else {
                this.left.add(newNode);
            }
        }
        else {
            if (this.right === undefined) {
                this.right = newNode;
            }
            else {
                this.right.add(newNode);
            }
        }

        if (this.rightHeight() - this.leftHeight() > 1) {
            // 右子树下的（左子树高度大于右子树高度，需要先进行右旋转）
            if (this.right !== undefined && this.right.leftHeight() > this.right.rightHeight()) {
                this.right.rightHeight();
            }
            this.leftRotate();
        }
        else if (this.leftHeight() - this.rightHeight() > 1) {
            // 左子树下的（右子树高度大于左子树高度，需要先进行左旋转）
            if (this.left !== undefined && this.left.rightHeight() > this.left.leftHeight()) {
                this.left.leftRotate();
            }
            this.rightRotate();
        }
    }

    /**
     * @description 左旋转
     * @example
     * 1. 创建一个新节点，值为当前节点的值
     * 2. 新节点左节点指向当前节点的左节点
     * 3. 新节点右节点指向当前节点的右节点下的左节点
     * 4. 当前节点的值变为右节点的值
     * 5. 当前节点的右节点指向右节点的右节点
     * 6.当前节点的左节点指向新节点
     */
    public leftRotate() {
        const newNode = new TreeNode(this.value);
        newNode.left = this.left;
        if (this.right !== undefined) {
            newNode.right = this.right.left;
            this.right.left = undefined;
            this.value = this.right.value;
            this.right = this.right.right;
        }
        this.left = newNode;
    }

    public rightRotate() {
        const newNode = new TreeNode(this.value);
        newNode.right = this.right;
        if (this.left !== undefined) {
            newNode.left = this.left.right;
            this.left.right = undefined;
            this.value = this.left.value;
            this.left = this.left.left;
        }
        this.right = newNode;
    }

    public height(): number {
        return Math.max(
                this.left === undefined ? 0 : this.left.height(),
                this.right === undefined ? 0 : this.right.height()
            ) + 1;
    }

    public leftHeight() {
        if (this.left === undefined) {
            return 0;
        }
        return this.left.height();
    }

    public rightHeight() {
        if (this.right === undefined) {
            return 0;
        }
        return this.right.height();
    }
}

/**
 * @description 平衡排序二叉树，左右两个子树的高度差绝对值不超过1
 */
export default class AVLBinarySortTree {
    private root!: TreeNode;
    
    public add(value: number) {
        const newNode = new TreeNode(value);
        if (this.root === undefined) {
            this.root = newNode;
        }
        else {
            this.root.add(newNode);
        }
    }

    public middle(node: TreeNode = this.root, res: number[] = []) {
        if (node.left !== undefined) {
            this.middle(node.left, res);
        }
        res.push(node.value);
        if (node.right !== undefined) {
            this.middle(node.right, res);
        }
        return res;
    }

    public height() {
        if (this.root === undefined) {
            return 0;
        }
        return this.root.height();
    }

    public leftHeight() {
        if (this.root === undefined) {
            return 0;
        }
        return this.root.leftHeight();
    }

    public rightHeight() {
        if (this.root === undefined) {
            return 0;
        }
        return this.root.rightHeight();
    }
}